package com.dh.leetcode.one;

import org.junit.Assert;
import org.junit.Test;

/**
 * @ClassName: _134_Gas_station
 * @Description: 134. 加油站
 * <p>
 * https://leetcode-cn.com/problems/gas-station/
 * <p>
 * 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * <p>
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * <p>
 * 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/gas-station
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2020/11/18 19:22
 */
public class _134_Gas_station {
    //从任意加油站开始，环一周看油量是否大于0
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        for (int i = 0; i < len; i++) {
            int oil = 0;
            for (int j = i; j < i + len; j++) {
                int index = j % len;
                int speed = gas[index] - cost[index];
                oil += speed;
                if (oil < 0) {
                    break;
                }
            }
            if (oil >= 0) {
                return i;
            }
        }
        return -1;
    }

    @Test
    public void canCompleteCircuitTest() {
        int[] gas = new int[]{1, 2, 3, 4, 5};
        int[] cost = new int[]{3, 4, 5, 1, 2};
        Assert.assertEquals(3, canCompleteCircuit(gas, cost));
    }


}
